/*************************************************************************
    > File Name: dijset.c
    > Author: botao
    > Mail: peng.botao@aliyun.com 
    > Created Time: Mon 24 May 2021 07:40:48 PM CST
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define VERTICES 6


void initialize(int parent[],int rank[]){
    int i;
    for(i = 0; i<VERTICES; i++){
        parent[i] = -1;
        rank[i] = 0;
    }
}

int find_root(int x, int parent[]){
    int x_root = x;
    while (parent[x_root] != -1){
        x_root = parent[x_root];
    }
    return x_root;

}

/* 1-UNION successfully, 0=failed*/
int union_vertices(int x, int y, int parent[], int rank[]){
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root == y_root){
        return 0;
    }
    else {
        if(rank[x_root] > rank[y_root])
            parent[y_root] = x_root;
        else if(rank[y_root]>rank[x_root]) {
            parent[x_root] = y_root;
        }
        else {
            parent[x_root] = y_root;
            rank[y_root]++;
        }
        return 1;
    }

}

int main(){
    
    /*
    
    */

    int parent[VERTICES] = {0};
    int edges[5][2] = {
        {0,1},{1,2},{1,3}, {3,4},{2,5}
    };
    int rank[VERTICES] = {0};
    initialize(parent,rank);
    int i;
    for(i=0;i<5;i++){
        int x = edges[i][0];
        int y = edges[i][1];
        if(union_vertices(x, y, parent,rank) == 0){
            printf("Cycle detected!\n");
            exit(0);
        }
    }
    printf("No Cycles found.\n");
    return 0;
}